def isValid(self, s):
    stack = []
    hash = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    for c in s:
        if c not in hash:
            stack.append(c)
        elif not stack or hash[c] != stack.pop():
            return False
    return not stack